#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    int dir[2][4] = { {0, 1, 0, -1}, {1, 0, -1, 0} };
    int dfs(vector<vector<bool>>& vis, const vector<vector<char>>& grid, int x, int y)
    {
        if (vis[x][y] || grid[x][y] == '0')
            return 0;
        vis[x][y] = true;
        for (int i = 0; i < 4; i++)
        {
            int a = x + dir[0][i];
            int b = y + dir[1][i];
            if (a >= 0 && a < grid.size() && b >= 0 && b < grid[0].size())
                dfs(vis, grid, a, b);
        }
        return 1;
    }
    int numIslands(vector<vector<char>>& grid) {
        int n = grid.size(), m = grid[0].size();
        int res = 0;
        vector<vector<bool>> vis(n, vector<bool>(m, false));
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                res += dfs(vis, grid, i, j);
        return res;
    }
};